package bin_tree.oj;

import java.util.LinkedList;
import java.util.Queue;

public class isCompleteTree {
    /**
     * 判断是否是完全二叉树，分为两个阶段，
     * 第一阶段是同时有左子树和右子树的节点，一只层序入队。
     * 遇到只有左子树的节点或者没有子树的节点，进入下一阶段
     * 第二阶段为叶子节点，往后的节点不可能有子树。
     * @param root
     * @return
     */
    public boolean isCompleteTree1(TreeNode root){
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        //引入标志位思想，方便第一第二阶段跳转
        boolean isSecondStep = false;
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(!isSecondStep){
                //第一个情况，左树和右树都存在
                if(cur.left != null && cur.right != null){
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }else if(cur.left == null && cur.right != null){
                    //只有右树没有左树，×
                    return false;
                }else if(cur.left != null) /**cur.right == null*/{
                    queue.offer(cur.left);
                    isSecondStep = true;
                }else {
                    //cur.left == null && cur.right == null
                    isSecondStep = true;
                }
            }else {
                //第二阶段，节点不可能存在子树
                if (cur.left != null || cur.right != null){
                    return false;
                }
            }
        }
        return true;
    }
}
